package cn.yuemouren.unionfind.impl;

import cn.yuemouren.unionfind.UnionFind;

/**
 * @Author: Timi
 * @Description:  第一种是实现方法 quick serch
 * @Date: 2020/7/12 16:57
 * @Version: v1.0
 */
public class UnionFindImpl1 implements UnionFind {

    private int[] data;

    public UnionFindImpl1(int size) {
        this.data = new int[size];
        for (int i = 0; i < data.length; i++)
            data[i] = i;
    }

    /**
     * 向并查集中添加元素
     * @param p
     * @param q
     * 时间复杂度是O(N)
     */
    @Override
    public void union(int p, int q) {
        int pValue = find(p);
        int qValue = find(q);

        if(pValue == qValue)
            return;
        for (int i = 0; i < data.length; i++){
            if(data[i] == pValue)
                data[i] = qValue;
        }
    }

    /**
     * 查看并查集中是否关联
     * @param p
     * @param q
     * @return
     * 时间复杂度是O(1)
     */
    @Override
    public boolean isConnectioned(int p, int q) {
        return find(p) == find(q);
    }

    /**
     * 根据值查找索引
     * @param i
     * @return
     */
    private int find(int i){
        if(i < 0 || i >= data.length)
            throw new IllegalArgumentException("param is fail");
        return data[i];
    }
}
